package arithmetic3.sort;

import java.util.Arrays;

/**
 * @author 姚凤桥
 * @Date 2021/12/15 9:43
 * @Description: 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int arr[] = {8, 8, 7, 43, 5, 1, 67, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            //将数组划分为两段
            int i = partition(arr, start, end);

            //将左边和右边分别进行排序
            quickSort(arr, start, i - 1);
            quickSort(arr, i + 1, end);
        }
    }

    public static int partition(int[] arr, int start, int end) {
        int i = start;
        int j = end;
        //将数组第一个元素作为划分标准
        int temp = arr[i];
        while (i != j) {
            //从右往左开始扫描，将第一个扫描到的小于temp的元素放到i位置
            while (i < j && arr[j] >= temp) {
                j--;
            }
            arr[i] = arr[j];

            //从左往右开始扫描，将第一个扫描到的大于temp的元素放到j位置
            while (i < j && arr[i] <= temp) {
                i++;
            }
            arr[j] = arr[i];
        }
        //此时i=j，将temp放在中间位置
        arr[i] = temp;
        return i;
    }
}

